package mo.tags.greedy;

public class L55 {

    public boolean canJump(int[] nums) {
        /*
         * int n = nums.length;
         * int right = 0;
         * for (int i = 0; i < n; i++) {
         *     if (i <= right) {
         *         right = Math.max(right, i + nums[i]);
         *         if (right >= n -1) {
         *             return true;
         *         }
         *     }
         * }
         * return false;
         */
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 0; i < n - 1; i++) {
            if (dp[i]) {
                for (int j = i+1; j < i+1+nums[i] && j < n; j++) {
                    dp[j] = true;
                }
            }
        }
        return dp[n-1];
    }

}
